/*
 * This file is part of LexiToolsMobile
 *  
 * Author: Jerzy Wawro
 * ver. 1.00
 * Copyright: Tenar (http://www.tenar.pl)
 *
 * Mobile LexiTools is an open source project; you can redistribute it 
 * and/or modify it under the terms of the license as published -  GPL with 
 * the following modification:  fragments of the code may be not copyleft 
 * (hidden), to protect contents of the dicionaries.
 * In this case the author of non-public fragments of the code is obliged 
 * to make available functionally equivalent code for unprotected dictionaries.
 * 
 * Mobile LexiTools is distributed WITHOUT ANY WARRANTY.
 * See the license for more details.
 *  
 * You should have received a copy of the GNU General Public License
 * along with LexiToolsMobile (see: gpl.txt); if not - you can find it 
 * on web page http://www.fsf.org/, or write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
package dict;

class iPage {
  static int PG_SIZE = 512;
  static int ITM_SIZE = 9; /* 4 klucz + 2 wskaznik do podstron + 3 wskaznik do danych */
  static int ITEMS_PER_PAGE = (int)((PG_SIZE -2) / ITM_SIZE); /* 2 na wskaznik do mniejszych */
  static int KEYS_AREA_SIZE = ITEMS_PER_PAGE * 4;
  static boolean littleEndianData = true;
  
  cache pgcache;
  byte[] buffer;
  byte[] sel_key;

  public iPage( cache p_cache ) {
      pgcache = p_cache;
      sel_key = new byte[4];
  }
  
  /* zapozyczone z projektu dorade */
  protected static short grabShort(byte[] bytes, int offset) {
        int ndx0 = offset + (littleEndianData ? 1 : 0);
        int ndx1 = offset + (littleEndianData ? 0 : 1);
        // careful that we only allow sign extension on the highest order byte
        return (short)(bytes[ndx0] << 8 | (bytes[ndx1] & 0xff));
    }
  
  /* --- */
  protected static byte grabByte(byte[] bytes, int offset) {
        return (bytes[offset]);
    }

  protected static void grabKey(byte[] bytes, int offset, byte[] key) {
        key[0]=bytes[offset];
        key[1]=bytes[offset+1];
        key[2]=bytes[offset+2];
        key[3]=bytes[offset+3];
    }

  void GetPage(pgfile pgf, short pgref)
  {
      buffer = pgcache.getpage(pgf,pgref).buffer;
  }

  void selectKey(int ix) {
    grabKey(buffer, 2 + ix * 4, sel_key); 
  }

  short bkpgref() { return grabShort( buffer,0);  }

  byte[] key(int ix)
  {
      selectKey(ix);
      return sel_key;
  }
  
  short dt1(int ix){ return grabShort(buffer, 2 + KEYS_AREA_SIZE + ix*2); }
  
  byte dt2(int ix) { return grabByte(buffer, 2 + KEYS_AREA_SIZE + ITEMS_PER_PAGE*2 + ix); }
   
  short pgref(int ix) { 
      return grabShort(buffer, 2 + KEYS_AREA_SIZE + ITEMS_PER_PAGE*3 + ix*2); 
  }   

}

class iResult
{
    int ptr1;
    int ptr2;
    byte[] key;

    iResult() {
        ptr1=0;
        ptr2=0;
        key=null;
    }

    iResult(byte[] k, int p1, byte p2) {
        int i;
        
        ptr1=p1;
        ptr2=p2;
        key=new byte[4];
        if (k != null)  for (i=0;i<4;i++) {  key[i]=k[i]; }
    }
    
    void setKey(byte[] k) {
        int i;
        for (i=0; i<4; i++) key[i]=k[i];
    }

    String skey()
    {
        return new String(key,0,4);
    }
}

public class btree {
    
 static int[] collate = {
   0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3A,0x3B,0x80,0x3D,0x81,0x3F,0x40,0x41,0x43,0x44,0x46,0x47,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,0x51,0x52,0x54,0x56,0x57,0x58,0x59,0x5B,0x5C,0x5D,0x5E,0x5F,0x60,0x61,0x64,0x65,0x66,0x67,0x68,0x69,0x6A,0x6C,0x6D,0x6F,0x70,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x7A,0x7B,0x7D,0x7F,0x82,0x83,0x84,0x86,0x87,0x88,0x89,0x8A,0x8B,0x8C,0x8F,0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,0x5A,0xA0,0xA1,0x62,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0x85,0xAE,0xAF,0x8D,0xB0,0xB1,0xB2,0x50,0xB3,0x42,0xB4,0xB5,0xB6,0xB7,0xB8,0xB9,0xBA,0xBB,0xBC,0x63,0xBD,0xBE,0xBF,0x79,0xC0,0xC1,0xC2,0xC3,0xC4,0x6B,0xC5,0xC6,0xC7,0xC8,0xC9,0x8E,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,0x45,0xD0,0xD1,0xD2,0x48,0xD3,0xD4,0xD5,0xD6,0xD7,0xD8,0x53,0xD9,0x55,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,0xE8,0xE9,0xEA,0xEB,0x6E,0xEC,0xED,0xEE,0x71,0xEF,0xF0,0xF1,0xF2,0xF3,0xF4,0x7C,0xF5,0x7E,0xF6,0xF7,0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0x81,0x80,0xFF
 };

 cache memcache;
 iPage pg;
 
 short[] path_pg; /* Numer strony przeszukiwanej */
 int[] path_ix; /* Indeks tablicy kluczy na tej stronie  */
 int level = 0;/* poziom (wskaznik w liscie Path) */

 pgfile pgf; /*  Ppgfile - plik w kt?rym przechowuje sie strony */
 short root; /* Nr strony - korzenia drzewa */
 boolean ok;
 byte[] keystr4;
 
 btree(pgfile p_file, short p_root)
 {
   pgf = p_file;
   root = p_root;
   level = 0;
   path_pg = new short[10];
   path_ix = new int[10];
   memcache = new cache();
   ok = true;
   keystr4=new byte[4];
   pg = new iPage(memcache);
}

 int icomp0(byte[] k1, byte[] k2, short dt10, short dt20, byte dt11, byte dt21)
 {
     int i, c1, c2;

        i=0;
        while (i<=3) {
            if (k1[i]!=k2[i]) {
                if (k1[i]==0) {
                    return -1; 
                }
                else if (k2[i]==0) {
/*
 if (dt20==0)  return 0; //? znajduje krotsze klucze1; 
                    else */
                    return 1;
                }
                if (k1[i]<0) { 
                    c1 = 256+k1[i];
                }
                else { c1=(int)k1[i];}
                if (k2[i]<0) { 
                    c2 = 256+k2[i]; 
                }
                else { 
                    c2=(int)k2[i];
                }
                if ((c1<0x20) || (c2<0x20)) return -1;
                return collate[ c1 - 0x20 ] - collate[ c2 - 0x20 ];
            }
            i++;
        }
        if ((dt20==0) && (dt21==0)) {
            return 0;
         }
        else if (dt10<dt20) {
            return -1;
         }
        else if (dt10>dt20) {
            return 1;
         }
        else if (dt11<dt21) {
            return -1;
         }
        else if (dt11>dt21) {
            return 1;
         }
        else {
            return 0;
         }
  }

 int ch2int(char c)
 {
    int res;
    
     res=(int)c;
          // utf8 -> win1250
     if (res>128) {
            if (res==261) res=185;
            else if (res==263) res=230;
            else if (res==281) res=234;
            else if (res==322) res=179;
            else if (res==324) res=241;
            else if (res==243) res=243;
            else if (res==347) res=156;
            else if (res==378) res=159; //191
            else if (res==380) res=191; //159
            else if (res==260) res=165;
            else if (res==262) res=198;
            else if (res==280) res=202;
            else if (res==321) res=163;
            else if (res==323) res=209;
            else if (res==211) res=211;
            else if (res==346) res=140;
            else if (res==377) res=175;
            else if (res==379) res=143;
            else res=32;
      }
     return res;     
 }
 
 int icomp(byte[] k1, byte[] k2)
 {
     int i, c1, c2;
/*
        String s1 = new String(k1,0,4);
        System.out.println(s1);
        String s2 = new String(k2,0,4);
        System.out.println(s2);
*/
        i=0;
        while (i<=3) {
            if (k1[i]!=k2[i]) {
                if (k1[i]==0) {
                    return -1; 
                }
                else if (k2[i]==0) {
                    return 1;
                }
                if (k1[i]<0) { 
                    c1 = 256+k1[i];
                }
                else { c1=(int)k1[i];}
                if (k2[i]<0) { 
                    c2 = 256+k2[i]; 
                }
                else { 
                    c2=(int)k2[i];
                }
                if ((c1<0x20) || (c2<0x20)) return -1;
                return collate[ c1 - 0x20 ] - collate[ c2 - 0x20 ];
            }
            i++;
        }
        return 0;
  }

 int icomps(String k1, String k2)
 {
     int i, l, c1, c2;
     
     
        l=k1.length();
        if (k2.length()<l) l=k2.length();
        i=0;
        while (i<=l) {
            c1=ch2int(k1.charAt(i));
            c2=ch2int(k2.charAt(i));
            if (c1!=c2) {
                if ((c1<0x20) || (c2<0x20)) return -1;
                return collate[ c1 - 0x20 ] - collate[ c2 - 0x20 ];
            }
            i++;
        }
        if (k2.length()>l) return -1;
        else if (k1.length()>l) return 1;
        else return 0;
  }

  void open()
  { /* Otwarcie pliku indeksowego  */
    level = 0;
  }

  void close()
  {
    pgf.close();
  }


  void next_level(short pg, int ix)
  {
   path_pg[level] = pg;
   path_ix[level] = ix;
   level = level + 1;
  }

boolean findkey(String keystr, iResult result)
  {
      short pgref;
      int pr, R,L;
      int i, i0, i1, l, C;

      l=keystr.length();
      if (keystr.startsWith("prze")) {
          i1=1;
          i0=4;
          keystr4[0]=(byte)'<';
      } else if (keystr.startsWith("przy")) {
          i1=1;
          i0=4;
          keystr4[0]=(byte)'>';
      } else {
          i1=0;
          i0=0;
      }
      for (i=i0;i<l && i1<4; i++) {
          C=ch2int(keystr.charAt(i));
          keystr4[i1]=(byte)C;
          i1++;
      }
      for (i=i1;i<4;i++) {keystr4[i]=' ';}
      pgref = root;
      ok = false;
      level = 0;
      pr=0;
      while ( (pgref > 0) && (!ok) ) {
                pg.GetPage(pgf, (short)pgref);
                pg.selectKey(pr);
                L = 1;  // wskaznik do pierwszego klucza 
                R = (short)pg.ITEMS_PER_PAGE; // wskaznik do ostatniego klucza
                while ((pg.key(R-1)[0] == 0) && (R>0)) R--;
                do { 
                    // przeszukiwanie polowkowe
                    pr = (L + R) / 2;
                    C = icomp(pg.key(pr-1),keystr4);
                        if (C >= 0)  R = pr - 1;
                        if (C <= 0)  L = pr + 1;
                } while (R >= L);
                if (L - R > 1) { // znaleziony wskaznik do danych}
                    next_level(pgref,pr);
		    ok = true;
		}
                else if (R <= 0) { // wskazuje element zerowy
                    next_level(pgref,0);
                    pgref = pg.bkpgref();
		}
		else {
                    next_level(pgref,R);
                    pgref = pg.pgref(R-1); // pobranie wskaznika do strony ponizej
                }
        }
        result.setKey(pg.key(pr-1));
        result.ptr1=pg.dt1(pr-1);
        result.ptr2=pg.dt2(pr-1);
        return ok;
  }

  
boolean nextkey(iResult result)
{
// pobranie nastpnego klucza
    int x;
    short pgref;
    byte[] k;

    ok = false;
    x=0;
    if (level == 0) { // czy pierwszy poziom poszukiwan
	pgref = root;
	while (pgref > 0) { //  znalezienie strony nastepnego klucza -    na najnizszym poziomie
            next_level(pgref,0);
            pg.GetPage(pgf,pgref);
            pgref = pg.bkpgref();
	}
	if (level != 0) { ok=true; x=1;} else { ok = false; }
    }
    else {
        // znalezienie strony najnizszego poziomu
        pg.GetPage(pgf,path_pg[level-1]);
        x=path_ix[level-1];
        if (x==0) {pgref=pg.bkpgref();}
        else {pgref = pg.pgref(x-1);}
        if (pgref>0) {
            while (pgref > 0 ) {
                pg.GetPage(pgf,pgref);
                if (pg.bkpgref() ==0) { next_level(pgref,1); }
                else next_level(pgref,0);
                pgref = pg.bkpgref();
            }
            x=1;
            ok=true;
        }
        else {
            while (((x>=pg.ITEMS_PER_PAGE) || (pg.key(x)[0]==0)) &&
                   (level>1)){
                level=level-1;
                x=path_ix[level-1];
                pg.GetPage(pgf,path_pg[level-1]);
            }
            if ((x<pg.ITEMS_PER_PAGE) && (pg.key(x)[0]!=0) &&
                   (level>=1)) {
                ok=true;
                x=x+1;
                path_ix[level-1]=x;
            }
	}
    }
    pg.GetPage(pgf,path_pg[level-1]);
    result.setKey(pg.key(x-1));
    result.ptr1=pg.dt1(x-1);
    result.ptr2=pg.dt2(x-1);
    return ok;
}

boolean prevkey(iResult result) {
    int level0, x;
    short pgref;

    ok = false;
    level0=level;
    x=0;

    ok = false;
    if (level == 0) return false;
    level0=level;
    x=path_ix[level-1]-1;
    pg.GetPage(pgf,path_pg[level-1]);
    while ( (level>0) && (x<0) || ((x==0) && ((pg.bkpgref()==0) || (level0!=level))) ) {
                level=level-1;
                x=path_ix[level-1];
                pg.GetPage(pgf,path_pg[level-1]);
    }
    if (level==0) {
        return false;
    }
    if ((x!=path_ix[level-1]) || (x==0)) {
            path_ix[level-1]=x;
            if (x>0) {
                pgref = pg.pgref(x-1);
            }
            else {
                pgref = pg.bkpgref();
            }
            while (pgref>0) {
                pg.GetPage(pgf,pgref);
                x=pg.ITEMS_PER_PAGE;
                while ((x>0) && (pg.key(x-1)[0]==0)) {
                    x--;
                }
                if (x>0) {
                    next_level(pgref,x);
                    pgref = pg.pgref(x-1);
                }
                else {
                    pgref = pg.bkpgref();
                }
            }
    }
    ok=true;
    x=path_ix[level-1];
    pg.GetPage(pgf,path_pg[level-1]);
    result.setKey(pg.key(x-1));
    result.ptr1=pg.dt1(x-1);
    result.ptr2=pg.dt2(x-1);
    return true;
}

boolean firstkey(iResult result)
 {
	level = 0;
	return (nextkey(result));
 }


void pg_boundary(iResult low, iResult high)
{
    int x;
    short pgref;
    
    if (level == 0) {  pgref=root;  }
    else {
        pgref=path_pg[level-1];
    }
    pg.GetPage(pgf,pgref);
    x=pg.ITEMS_PER_PAGE;
    while ((x>0) && (pg.key(x-1)[0]==0)) {
       x--;
    }
    low.setKey(pg.key(0));
    low.ptr1=pg.dt1(0);
    low.ptr2=pg.dt2(0);
    high.setKey(pg.key(x-1));
    high.ptr1=pg.dt1(x-1);
    high.ptr2=pg.dt2(x-1);
}

boolean pg_prev(iResult result)
{
    if (level == 0) {  return false;  }
    else {
        path_ix[level-1]=1;
        return prevkey(result);
    }
}

boolean pg_next(iResult result)
{
    int x;
    short pgref;

    if (level == 0) {  return false;  }
    else {
        pgref=path_pg[level-1];
        pg.GetPage(pgf,pgref);
        x=pg.ITEMS_PER_PAGE;
        while ((x>0) && (pg.key(x-1)[0]==0)) {
            x--;
        }
        path_ix[level-1]=x;
        return nextkey(result);
    }
}

}
